package 牛客网在线编程题库;

/**
 * 已知一个背包最多能容纳物体的体积为V
 * 现有n个物品第i个物品的体积为vi
 * ​
 * 第i个物品的重量为wi
*
 * 求当前背包最多能装多大重量的物品
 * 示例1
 * 输入
 * 10,2,[[1,3],[10,4]]
 * 返回值
 * 4
 * 说明
 * 第一个物品的体积为1，重量为3，第二个物品的体积为10，重量为4。只取第二个物品可以达到最优方案，取物重量为4
 */

public class _01背包 {
    public static void main(String[] args) {
        // 背包容量
        int V = 10;
        // 物品个数
        int n = 2;
        // 物品体积和对应重量
        int[][] vm = {
                {1, 3},
                {10, 4}
        };
        int target = knapsack(V, n, vm);
        System.out.println(target);
    }

    public static int knapsack (int V, int n, int[][] vw) {
        // 定义二维数组dp，dp[i][j]表示在i件商品，背包容量为j的情况下能取得的最大的价值量
        int[][] dp = new int[n + 1][V + 1];
        // 初始化，0件商品可以组成的最大的价值量是0，背包容量为0亦是如此
        for (int i = 0 ; i <= n ; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0 ; i <= V ; i++) {
            dp[0][i] = 0;
        }
        // 遍历求解dp数组
        for (int i = 1 ; i <= n ; i++) {
            for (int j = 1 ; j <= V ; j++) {
                // 若此时当前物品容量大于背包剩余容量
                if (j < vw[i - 1][0]) {
                    dp[i][j] = dp[i - 1][j];
                }else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - vw[i - 1][0]] + vw[i - 1][1]);
                }
            }
        }
        return dp[n][V];
    }
}
